#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@sharp>
#
# Distributed under terms of the MIT license.

"""
https://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0?tpId=13&&tqId=11212&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
"""


class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def Print(self, pRoot):
        if pRoot is None:
            return []

        self.results = []
        self.queue = [
            [],
            [pRoot]
        ]

        while True:
            if not self.queue[1]:
                break

            print('while 0')
            self.put_negative()

            if not self.queue[0]:
                break

            print('while 1')
            self.put_positive()

        return self.results

    def put_positive(self):
        # 逆序访问 self.queue[0], 正序放入 self.queue[1]
        assert not self.queue[1]

        tmp = []

        while self.queue[0]:
            n = self.queue[0].pop()     # 从尾部逆序访问
            tmp.append(n.val)

            # print('p a', self.results)

            if n.right:
                self.queue[1].insert(0, n.right)

            if n.left:
                self.queue[1].insert(0, n.left)

        self.results.append(tmp)

        return

    def put_negative(self):
        # 正序访问 self.queue[1], 正序放入 self.queue[0]
        assert not self.queue[0]

        tmp = []
        while self.queue[1]:
            n = self.queue[1].pop(0)
            tmp.append(n.val)

            if n.left:
                self.queue[0].append(n.left)

            if n.right:
                self.queue[0].append(n.right)

        self.results.append(tmp)

        return


def test():
    s = Solution()

    r = TreeNode(0)
    rl = TreeNode(1)
    rr = TreeNode(2)
    r.left = rl
    r.right = rr

    rll = TreeNode(3)
    rlr = TreeNode(4)
    rl.left = rll
    rl.right = rlr

    rrl = TreeNode(5)
    rrr = TreeNode(6)
    rr.left = rrl
    rr.right = rrr

    e1 = TreeNode(7)
    e2 = TreeNode(8)
    rll.left = e1
    rll.right = e2

    ret = s.Print(r)
    print(ret)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
